package com.parsechina.hpush.broker;


import java.util.Random;

/**
 * Trie树
 *
 * @author heartraid
 */
public class StandardTrie {

    enum NodeKind {LN, BN};

    /**
     * Trie结点
     */
    static class TrieNode {

        char key;
        TrieNode[] points = null;
        NodeKind kind = null;
    }

    /**
     * Trie内部结点
     */
    static class BranchNode extends TrieNode {

        BranchNode(char k) {
            super.key = k;
            super.kind = NodeKind.BN;
            super.points = new TrieNode[30];
        }
    }

    /**
     * Trie叶子结点
     */
    static class LeafNode extends TrieNode {

        LeafNode(char k) {
            super.key = k;
            super.kind = NodeKind.LN;
        }
    }

    private TrieNode root = new BranchNode(' ');

    /**
     * 想Tire中插入字符串
     */
    public void insert(String word) {

        //System.out.println("插入字符串："+word);
        //从根结点出发
        TrieNode curNode = root;
        //为了满足字符串集合X中不存在一个串是另外一个串的前缀
        word = word + "$";
        //获取每个字符
        char[] chars = word.toCharArray();
        //插入
        for (int i = 0; i < chars.length; i++) {


            //System.out.println("   插入"+chars[i]);
            if (chars[i] == '$') {
                curNode.points[29] = new LeafNode('$');
                //	System.out.println("   插入完毕,使当前结点"+curNode.key+"的第26孩子指针指向字符：$");
            } else {

                int pSize = 0;
                if (chars[i] == '/') {
                    pSize = 0;
                } else if (chars[i] == '+') {
                    pSize = 1;
                } else if (chars[i] == '#') {
                    pSize = 2;
                } else {
                    pSize = chars[i] - 94;
                }
                if (curNode.points[pSize] == null) {
                    curNode.points[pSize] = new BranchNode(chars[i]);
                    //	System.out.println("   使当前结点"+curNode.key+"的第"+pSize+"孩子指针指向字符: "+chars[i]);
                    curNode = curNode.points[pSize];
                } else {
                    //	System.out.println("   不插入，找到当前结点"+curNode.key+"的第"+pSize+"孩子指针已经指向字符: "+chars[i]);
                    curNode = curNode.points[pSize];
                }
            }
        }
    }

    /**
     * Trie的字符串全字匹配
     */
    public boolean fullMatch(String word) {

        //System.out.print("查找字符串："+word+"\n查找路径：");
        //从根结点出发
        TrieNode curNode = root;

        word = word + "$";

        //获取每个字符
        char[] chars = word.toCharArray();

        for (int i = 0; i < chars.length; i++) {
//            System.out.println(chars[i] + " -> ");
            int pSize = 0;
            if (chars[i] == '/') {
                pSize = 0;
            } else if (chars[i] == '+') {
                pSize = 1;
            } else if (chars[i] == '#') {
                pSize = 2;
            } else if (chars[i] == '$') {
                pSize = 29;
            } else {
                pSize = chars[i] - 94;
            }
            if (curNode.points[pSize] == null) {
                //	System.out.println(" 【失败】");
                return false;
            } else {
                curNode = curNode.points[pSize];
            }
        }
        if (curNode.key == '$') {
//            System.out.println('&');
            //	System.out.println(" 【成功】");
            return true;
        }
        //	System.out.println("  【失败】");
        return false;
    }


    /**
     * 先根遍历Tire树
     */
    private void preRootTraverse(TrieNode curNode) {

        if (curNode != null) {
            System.out.print(curNode.key + " ");
            if (curNode.kind == NodeKind.BN)
                for (TrieNode childNode : curNode.points)
                    preRootTraverse(childNode);
        }

    }

    /**
     * 得到Trie根结点
     */
    public TrieNode getRoot() {
        return this.root;
    }

    public static String getRandomString(int length){
        String str="abcdefghijklmnopqrstuvwxyz";
        Random random=new Random();
        StringBuffer sb=new StringBuffer();
        for(int i=0;i<length;i++){
            int number=random.nextInt(26);
            sb.append(str.charAt(number));
        }
        return sb.toString();
    }

    /**
     * 测试
     */
    public static void main(String[] args) {

        StandardTrie trie = new StandardTrie();
        trie.insert("bear");
        trie.insert("bell");
        trie.insert("bid");
        trie.insert("bull");
        trie.insert("buy");
        trie.insert("sell");
        trie.insert("stock");
        trie.insert("/stop");

        System.out.println(getRandomString(16));
        String searchWord = null;
        for (int i=0; i<1000000;i++) {
            searchWord = getRandomString(10);
            trie.insert(searchWord);
        }

        System.out.println(searchWord);
        long nastart = System.nanoTime();
        for (int i = 0; i < 100; i++) {
            trie.fullMatch(searchWord);
        }
        long naend = System.nanoTime();
        System.out.println("== 用时: " + (naend - nastart) / 1000);
        System.out.println(trie.fullMatch("/stop"));
    }
}
